package org.example.myleet.p775;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return true;
        }
        //题目转换个意思就是如果存在不是局部倒序的全局倒序则返回false，使用小根堆保存[i+1]后缀中最小的数
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.naturalOrder());
        boolean[] visited = new boolean[nums.length];
        visited[nums[0]] = true;
        visited[nums[1]] = true;
        for (int i = 2; i < n; ++i) {
            pq.offer(nums[i]);
        }
        for (int i = 2; i < n; ++i) {
            Integer peek = pq.peek();
            while (null != peek && visited[peek]) {
                //如果已经走过的数字，则弹出小根堆
                pq.poll();
                peek = pq.peek();
            }
            if (null != peek && nums[i - 2] > peek) {
                //存在不是局部倒序的全局倒序则返回false
                return false;
            }
            //已经走过的数字
            visited[nums[i]] = true;
        }
        return true;
    }
}
